\documentclass[12pt, a4paper]{article}

\usepackage{a4}
\usepackage{graphicx}
\usepackage{times}
\usepackage{url}
\usepackage{float}

% If you would like to write in danish uncommehttp://www.daimi.au.dk/~u062870/p2p/nt the following two lines.
%\usepackage[latin1]{inputenc}
%\usepackage[danish]{babel}


% Remember to state your full names and student IDs.
\author{Mirza Kapetanovic (20062870)\\
Mads Fabricius Schmidt (20061199)\\
Jakob Schultz-Nielsen (20061951)}

% prepend the title with your group name
\title{Hotel - P2PN Report 2010}

\begin{document}

\maketitle

\section{System Description}
\label{sec:system_description}

We would like to begin by describing how data is represented internally in the system. By doing so we hope the reader has a better understanding of how the different aspects of the system are tied together.

To describe how the system is implemented it is natural to begin by describing how we represent the peers. To represent our peers we choose to build a 4-tuple for each peer where we have a unique name, a max number of neighbors, an ip address and a port number. We chose tuples because they are immutable which guarantees that the correct data is in the correct position in the tuple. It is a simple, yet effective, way to represent peers, and can easily be transfered to other peers.\\

We also chose to represent files as tuples. These are 2-tuples with the name and size of the specific file. This almost completely guarantees that no two different files are represented as the same tuple. These tuples are then appended on the peers file list. When the peer gives his file list to his neighbor, his neighbor creates a 2-tuple with his name and his file list and appends this to his neighbor files list.\\

Next we have our communications protocol. When two peers are communicating with each other they use a standardized way of doing so. They send compressed tuples between each other on the form; the unique peer name, a command and optionally some data (if no data is needed to be sent it defaults to None). This was a design choice that came later on in order to make the communication between peers consistent and simple to understand. However we do now regret that we only include the unique peer name instead of the complete peer tuple, since this would have saved us a lot of iterations through the peer list.\\

Communicating between peers is a risky business and at first our threads crashed when they tried to communicate with peers which had disconnected on the network, so we implemented a basic PeerDisconnectedError to handle all socket errors. When a peer disappears from the network it might not be noticed at first. When it's neighbors try to ping it they will get a PeerDisconnectedError, and they will remove all the data that they have on that peer. However peers which aren't neighbors with the peer will still continue to think he's alive until they try to contact him and find him to be disconnected, which will then prompt them to remove all his data. This is not a problem since a peers peer list is only a list of potential peers and not a guaranteed state of the network.



%A thorough description of your system---with special focus on the P2P
%aspects.  How does your system solve its intended problem; how does it
%do what it does at run-time?  If there is a difference between your
%design and your implementation, you should be very specific in
%describing those differences.

%Remember to describe every single design choice and argument for the
%validity of those choices. 

%When describing your design you should relate your system to other
%systems---as e.g., the systems found in the curriculum. Citation is
%easy in LaTeX; e.g., ``as seen in Gia~\cite{Chawathe:2003ul}'' or
%``the Gnutella specification~\cite{gnutella-spec}''. All papers
%included in the curriculum can be found in the BiBTeX file that came
%with this report template. 


\subsection{Bootstrapping the system}
\label{sec:bootstrapping-system}

When a peer wants to enter the network it issues a hello request to a peer who is already in the network. The peer responds back by sending the requester his peer list. The initial peer then traverses the list and recursively sends hello requests to the peers in the given peer list. We of course check whether we've already visited a peer so as not to send two requests to the same peer.\\

We decided in the late phase of the development to issue a max number of peers in a peers peer list. This is due to the potential enormity of the network, which would then require each peer, upon initial connection, to traverse each and every peer in the network which would cause massive overload and a significant slowdown of the network. What is important for the network is not that each peer knows everyone in the network, but that it has a neighborhood where it can begin its search for files. For an example see figure \ref{bootstrapping}.\\

\begin{figure}
\centering
\includegraphics[scale=0.6]{bootstrapping.png}\\
\caption{A bootstrapping example.}
\label{bootstrapping}
\end{figure}

This is one of the reasons why we shuffle the retrieved peer lists before using them, by creating a random sequence of peers to visit, we hope to have a network where each peer has a small image of the system, but is in the whole connected together.\\

Pros:
\begin{itemize}
\item The system is simple and easy to understand.\\
\item Makes sure every peer that enters the network either has maxed out his peer list, or has the full network.\\
\end{itemize}

Cons:
\begin{itemize}
\item The system is based on the assumption that it is highly unlikely that a network will split up into two networks where  peers have no information about each others network.
\end{itemize}

%Describe how you bootstrap your P2P network. What are the pros and
%cons of your design in this regard?

\subsection{Finding Neighbours}
\label{sec:finding-neighbours}

When a peer has bootstrapped itself into the network, meaning that it has gathered a number of peers in it's peer list, it then tries to get some neighbors. Since a peer is interested in getting the best and most solid neighborhood possible, it creates a sorted list from the peer list. This list is sorted after the maximum number of peers each peer in the list has, since this would give the peer the best possible neighborhood. Meaning that the number of hops a file is away is minimal.\\

After sorting the list the peer begins issuing peer requests to the highest capacity peers and downward and continues to do so until it either has as many peers as its capacity allows, or it has asked every peer in its list. Issuing a neighbor request not only sends the neighbor command, but also sends the peer tuple and the current amount of neighbors. The latter piece of information is due to the dropping algorithm used by the receiving peer to decide whether a neighbor should be dropped in favor of another.\\

Now that we've talked about how a peer initiates a neighborhood, let's discuss how a peer handles an incoming neighbor request. The dropping/adopting algorithm nappend used by our peer to decide whether a neighbor is to be dropped in favor of another is a close cousin to the Gia~\cite{Chawathe:2003ul} pick\_neighbor\_to\_drop(X,Y) method. We will, however, take a step by step approach to explaining the algorithm.\\

\begin{figure}
\centering
\includegraphics[scale=0.6]{neighbor1.png}\\
\caption{A neighbor request example, part 1.}
\label{neighbor1}
\end{figure}


First we check whether we have room for another neighbor, if we do have room we merely add the peer which requested to become neighbors. Otherwise we sort our neighborhood list according to the maximum number of neighbors each neighbor peer is allowed to have. We then look at the last peer in the sorted list, if his number of maximum peers is larger than the maximum number of peers from to requester, we reject his neighbor request.\\

If the maximum number of neighbors is more than that of the lowest peer, we then try to find a suitable candidate,  meaning we find the neighbor with the largest current number of neighbors. So now we have a candidate to throw away and our requester. If the requesters maximum number of neighbors is larger than the maximum number of neighbors of any current neighbor or the candidates current number of neighbors is larger than the requesters current number of neighbors plus one (our hysteresis constant) then drop the candidate and accept the requester as a neighbor. For an example see figures \ref{neighbor1} and \ref{neighbor2}.\\

\begin{figure}
\centering
\includegraphics[scale=0.6]{neighbor2.png}\\
\caption{A neighbor request example, part 2.}
\label{neighbor2}
\end{figure}

While we would have liked to implement a strategy to constantly improve upon the overlay network, we have not found the time to do this. We would have liked to implement a variation of the satisfiability tactic also employed by Gia. The consequences of the lack of this technique, or other like it, is that our network only changes when a new peer tries to initiate itself into the network. Another consequence is that peers which have been dropped by some of their neighbors all of a sudden are isolated more and more from the center of the network, making files further an further away for the k-walker to reach.\\

While this could be helped simply by adding a clause, which tells a peer if he no longer has any neighbors, then he should initiate a new hello sequence to enter the network once again. However this wouldn't be as effective as a general optimization strategy for the entire network and would demand much more bandwidth since the initiation sequence communicates with many peers before having initiated completely.\\

Pros:
\begin{itemize}
\item The network finds the best possible neighborhood for a peer when it initiates.\\
\end{itemize}

Cons:
\begin{itemize}
\item The network degrades over time due to lack of real time optimization strategy.\\
\end{itemize}

\subsubsection{Maintaining the Neighborhood}
\label{mantaining-neighborhood}

To keep the neighborhoods up to date we use our pinger thread class. This class runs in its own seperate thread and pings all the neighbors every minute. This is done to make sure that the network is intact, by having all the peers keep track of their neighbors, and if a neighbor is suddenly unresponsive the peer can then remove the neighbor and all their data thereby making room for a new peer to join the neighborhood.\\

While the pinger class' most important job is to make sure that the current neighborhood is in fact valid, it also serves to keep the neighbors up to date when it comes to the files which the peer offers. When a file is modified in the peer, it creates a 3-tuple with the file tuple and the modified command (i.e. ADDED or REMOVED). We chose to send tuples of changes instead of the entire file catalog to save on the precious bandwidth. After all if all peers are going to send their entire file catalog each minute it would be an enormous strain on the network. Instead we only send the changes, if any have occured.\\

%Describe, in great detail and with figures, how you build your overlay
%network by using clever neighbourhood selection. What are the pros and
%cons of your approach?

\subsection{Searching the Network}
\label{sec:searching-network}

Searching in the network is implemented using random k-walkers. This means when peer p1 wants to search after a file file.txt (see figure \ref{walker}), he first checks if the file is present locally. That is if p1 itself has the file or if one of its neighbors (every peer has an index consisting of files its neighbors hold). If this is the case p1 can answer its own query, without ever contacting other peers.\\

\begin{figure}
\centering
\includegraphics[scale=0.5]{walker.png}\\
\caption{A search example.}
\label{walker}
\end{figure}

If we assume that the file is held by peer p27, which is not our neighbor, but can be reached through other peers. Since the file p1 wants is not local, it must initiate a search. p1 chooses at random k (k is set by the user) of its neighbors ans sends a find command with the file name, TTL (also configurable by the user) and information about itself as the requesting peer.\\

By using figure \ref{walker} as an example, we see p1 sends two walkers to p5 (a) and p10 (c). Each peer checks if they have the file locally. Since none of them does, they prepare to send the walker further. They each choose one of there neighbors at random, but excluding the peer they received the walker from, in this case p1. They decremeent the TTL parameter by one and check if it's zero, if it is they don't send the walker to other peers, it just dies. In the example they send the walker to the randomly choosen neighbors (b) and (d) by sending a find request. The walker dies in p12, since it has no neighbors to forward the request to. But p19 finds the requested file locally, since it is neighbor with p27, who is holding the file. By using the requestings peers information in the walker p19 contacts p1 directly (e) with a found command containing the file name and the p27's information. Now p1 has the option to open direct conection to p27 and request the file to download by sending a get command and p27 will respond by sending content of the file back to p1.\\

The biggest advantage in out implementation of the walker is its small use of the peer and the overall network resources. This kind of search dosen't generate a lot of trafic between peers and since we only care that the peer who requested the file gets the location, the peers don't need to hold extra state, which tells where the file is likelily to be, based on already seen queries. This also means the walkers size is constant, since it does not have the need to save a chain of peers, which it can latter use to backtrace its path and updating the individual peer's state (this in contrast to adaptive probalistic search). Communication between peers is reduced.

Besides from the low resource use, this implementation is simple. But it does not take some of the information available into consideration (see below).\\

This approach has some drawbacks. Since we forward the walker at random, we can't say much about its path in the network and its success rate. A network like GIA utilises biased walkers to improve searching. Since our peers hold the capacity of their neighbors, we could have used that information to favour peers with better capacity (knowing they will be better connected and better equipped to handle the load). By using an other GIA strategy where we let walkers from time to time contact the source peer to check if the requested file has been found could have been used. But depending on k and TTL this could have created more traffic.

%Describe, again in great detail and with illustrations, how searches
%are done in your system.\\



\section{Evaluation}
\label{sec:evaluation}

The biggest strength of the overall system is the small amount of traffic that is sent, through out the network. Only the needed messages, which contained short bits of information, are communicated from one peer to another. In our tests we could see that most of the time the network was idle, waiting for an event (like search for a file). This also meant that our peers didn't need much computer resources to run. 

But this came with some disadvantages. When initiated the network is built to be optimal but over time as peers are disconnected it degrades, with the risk of the newtork spliting in two.

Again while our walkers didn't take much bandwith, they could only make random choices as to where to go next. If the peers has kept some extra information, for example about the likely location fo a file, searching could have been more effective.\\

There are of course some major security flaws in the system. A malicious peer can disrupt the network flow. It is easy to overloard a peer, by for example sending neighborhood requests all the time, which take some time to proccess and the peer may need to contact other peers in the neighborhood to get some information. This can be costly to do.

Our system is not designed to protect users identity. In a file request the requesting peer's identity is given along the way, so it is always visible who is requesting which file, unlike in Freenet, where much is done to make peers anonymous and the content they are requesting encrypted. In that respect our system resembles more the bittorrent protocol. But a central part of the protocol is making sure the peers get the corret file (comparing pieces with the sha1 hash from the torrent file), our system is naive and accepts whatever is sent its way. This also means peers with dangerous content, can easly distribute it in the network.

%A short evaluation of your system showing off its strengths and
%weaknesses. Here is where you can test your neighbourhood selection
%algorithms against each other---if you have chosen to make more than
%one. This is also the place where you can test search strategies and
%perhaps the effects of one-hop replication.


\section{Conclusion}
\label{sec:conclusion}

Throughout the course we have encountered small and larger problems. These problems were typically related to how we represented the data and to how we communicated this data between peers. When we first started programming the system we represented the data almost specifically to the method we were coding at that time. Over time we found out, not to anyones surprise, that this way of deciding our data representation made coding other methods surprisingly difficult since we had no official protocol, which meant we had be absolutely sure how the specific piece of data we were using was built up. This lead us to refactor the entire system, making classes out of previously bloated methods and making data representation uniform. Despite this refactorisation there are still a few bad design choices left, such as using the unique peer name instead of the peer tuple in our communications protocol, however we did learn to appreciate having an overall data structure strategy before starting to code.\\

While the program works within the parameters of the exercises, it does have some flaws which makes it a less than ideal candidate to replace well established peer to peer programs. One such flaw is the lack of a real time network optimization strategy which we mentioned earlier. The lack of such a strategy almost surely dooms the network to degrade as more and more peers join the network and while new peers are added to the best possible neighborhoods, old peers, especially low capacity peers, are almost guaranteed to fall out of the network entirely and are forced to restart the program to enter the network again. Which is costly in bandwidth.\\



%What have you learnt? Is your solution viable? 

\appendix

\section{Using the System}
\label{sec:using-system}

Using the system

All the needed files (python modules) for running the program can be found here:

\begin{verbatim}
  http://www.daimi.au.dk/~u062870/p2p/p2p.zip
\end{verbatim}\section{Using the System}
\label{sec:using-system}


The system is run on a linux machine with python installed. A peer is started by isuing the following command in a linux terminal.

\begin{verbatim}
  $python main.py <name> <capacity> <port>
\end{verbatim}

With the following meaning.

\begin{description}
  \item[name] The unique network name of the peer.
  \item[capacity] Maximum number of neighbors the peer can have.
  \item[port] The port number on which the peer listens on for incoming connections.
\end{description}

After the start you will presented with a prompt, which you can use to issue commands to the peer. The following commands can be used.

\begin{itemize}

  \item Opens a connection to the peer given by the ip and port and boostraps itself by downloading the plist of the contacted peer.
  \begin{verbatim}
    peer> hello <ip>:<port>
  \end{verbatim}

  \item Lists all the known peers.
  \begin{verbatim}
    peer> plist
  \end{verbatim}
  
  \item Creates a graph with all the given peers and their neighbors. The specified peers must be present in plist.
  \begin{verbatim}
    peer> nlist [<peers>] [-o <file.dot>]
  \end{verbatim}
  
  \item List all local files (own and neighbors files).
  \begin{verbatim}
    peer> flist
  \end{verbatim}
  
  \item Searches for the file on the network.
  \begin{verbatim}
    peer> find <filename>
  \end{verbatim}
  
  \item Downloads the file from the peer given by the ip and port.
  \begin{verbatim}
    peer> get <filename> <ip>:<port>
  \end{verbatim}
  
  \item Searches for the fil\section{Using the System}
\label{sec:using-system}
e on the network and downloads if found.
  \begin{verbatim}
    peer> fget <filename>
  \end{verbatim}
  
  \item Adds random files from the current directory.
  \begin{verbatim}
    peer> random
  \end{verbatim}

\end{itemize}

%This appendix includes complete instructions on installing and using
%your system.  Please test your own zip-file on a fresh-horse host
%beforehand---if it doesn't work there we wont be able to test it.

\section{Network Graphs}
\label{sec:graphs}

\newpage

\begin{figure}[H]
\centering
\includegraphics[scale=0.20, angle=90]{trial8.png}\\
\caption{Example of a network created by our system.}
\label{trial8}
\end{figure}

\begin{figure}[H]
\centering
\includegraphics[scale=0.20, angle=90]{trial10.png}\\
\caption{Another example of a network created by our system.}
\label{trial10}
\end{figure}

\newpage

\bibliographystyle{plain}
\bibliography{literature}

\end{document}
